package com.programmercarl.greed;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * https://leetcode.cn/problems/merge-intervals/description/
 * 合并区间     AC
 *
 * @author yulongtian
 * @create 2025-02-08 21:50
 */
public class Test14 {
    public static void main(String[] args) {
//        int[][] intervals = {{2, 6}, {1, 3}, {15, 18}, {8, 16}};
        int[][] intervals = {{1, 4}, {2, 3}};
        Test14 test14 = new Test14();
        System.out.println(Arrays.deepToString(test14.merge(intervals)));
    }

    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0 || intervals.length == 1) {
            return intervals;
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
        });

        List<int[]> list = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            // 无重叠，添加结果
            if (intervals[i][0] > intervals[i - 1][1]) {
                list.add(new int[]{intervals[i - 1][0], intervals[i - 1][1]});
            } else {
                // 有重叠，则合并
                intervals[i][0] = intervals[i - 1][0];
                intervals[i][1] = Math.max(intervals[i - 1][1], intervals[i][1]);
            }
            if (i == intervals.length - 1) {
                list.add(new int[]{intervals[i][0], intervals[i][1]});
            }

        }
        int[][] result = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}
